#
# @lc app=leetcode.cn id=62 lang=python3
#
# [62] 不同路径
#

# @lc code=start
class Solution:
    def uniquePaths(self, m: int, n: int) -> int: 
        # 最后一步:右下角,dp[m-1][n-1]
        # dp[i][j]表示走到第i行第j列总共有多少条不同路径
        # 子问题:
        # 递推方程:dp[i][j]=dp[i-1][j]+dp[i][j-1]
        # 下标:走到第i行第j列
        # 循环顺序:i,j都是从小到大
        # 初始状态:dp[i][0]=1,dp[0][j]=1,第一行,第一列只有1条路径
        dp = [[1]*n for _ in range(m)]
        
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            #     print(f'dp[{i}][{j}]={dp[i][j]}', end=' ')
            # print()
            
        return dp[m-1][n-1]
# @lc code=end

